import java.util.Arrays;

public class Solution322 {
    public int coinChange(int[] coins, int amount) {
        int[] f=new int[amount+1];
        Arrays.fill(f,-1);
        f[0]=0;
        for (int coin : coins) {
            for (int i=coin;i<=amount;i++){
                if (f[i-coin]!=-1){
                    f[i]=f[i]==-1?f[i-coin]+1:Math.min(f[i],f[i-coin]+1);
                }
            }
        }
        return f[amount];
    }

    public static void main(String[] args) {
        System.out.println(new Solution322().coinChange(new int[]{1, 2, 5},11));
    }
}
